#include <bits/stdc++.h>
using namespace std;

/*
3347. 执行操作后元素的最高频率 II
已解答
困难
相关标签
premium lock icon
相关企业
提示
给你一个整数数组 nums 和两个整数 k 和 numOperations 。

你必须对 nums 执行 操作  numOperations 次。每次操作中，你可以：

选择一个下标 i ，它在之前的操作中 没有 被选择过。
将 nums[i] 增加范围 [-k, k] 中的一个整数。
在执行完所有操作以后，请你返回 nums 中出现 频率最高 元素的出现次数。

一个元素 x 的 频率 指的是它在数组中出现的次数。

 

示例 1：

输入：nums = [1,4,5], k = 1, numOperations = 2

输出：2

解释：

通过以下操作得到最高频率 2 ：

将 nums[1] 增加 0 ，nums 变为 [1, 4, 5] 。
将 nums[2] 增加 -1 ，nums 变为 [1, 4, 4] 。
示例 2：

输入：nums = [5,11,20,20], k = 5, numOperations = 1

输出：2

解释：

通过以下操作得到最高频率 2 ：

将 nums[1] 增加 0 。
 

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 109
0 <= k <= 109
0 <= numOperations <= nums.length
*/

// 法一
class Solution {
public:
    int maxFrequency(vector<int>& nums, int k, int numOperations) {
        sort(nums.begin(), nums.end()); // 排序便于区间元素统计（双指针基础）
        int l = 0, r = 0;
        int n = nums.size();
        int res = 0; // 记录最大频率
        int cnt = 0; // 记录当前元素在原数组中的频率

        // 以原数组中的元素为目标值x，计算最大可能频率
        for (int i = 0; i < n;) {
            int x = nums[i]; // 当前目标值x（原数组中的元素）

            // 统计x在原数组中的出现次数cnt（连续相同元素）
            const int prev = i;
            for (++i; i < n && x == nums[i]; ++i)
                ; // 跳过所有相同的x
            cnt = i - prev;

            // 双指针确定[x-k, x+k]区间：该区间内的元素可通过操作变为x
            while (nums[l] < x - k)
                ++l; // l移到区间左边界（>=x-k）
            while (r < n && nums[r] <= x + k)
                ++r; // r移到区间右边界（>x+k）

            // 当前x的最大频率：区间内元素总数（上限）与（原频率+可操作次数）的较小值
            res = max(res, min(r - l, cnt + numOperations));
            cnt = 0;
        }

        if (res >= numOperations)
            return res;

        // 处理目标值为非原数组元素的情况（需元素调整范围重叠）
        l = 0;
        for (r = 0; r < n; ++r) {
            // 区间内元素需满足：最大差距 <= 2k（才能通过调整到同一中间值）
            // 即nums[r] - nums[l] <= 2k → nums[l] >= nums[r] - 2k
            while (nums[l] < nums[r] - 2 * k)
                ++l;
            // 该区间内的元素可通过操作变为同一目标值，更新最大可能数量
            res = max(res, r - l + 1);
        }

        // 最终频率不超过可操作次数（因非原元素需全部操作）
        return min(res, numOperations);
    }
};

// 法二
class Solution {
public:
    int maxFrequency(vector<int>& nums, int k, int numOperations) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        unordered_map<int, int> freq; // 统计原数组元素频率
        for (int num : nums) {
            freq[num]++;
        }

        // 候选目标值集合（用long long避免溢出）
        unordered_set<long long> candidates; 
        for (int num : nums) {
            long long ll_num = num; // 转为long long处理大数值
            candidates.insert(ll_num);
            candidates.insert(ll_num - k); // 避免num - k溢出
            candidates.insert(ll_num + k); // 避免num + k溢出
        }

        int max_freq = 0;
        int remain = n - numOperations; // 未被操作的元素数量

        for (long long x : candidates) { // x用long long避免溢出
            // 计算目标x的调整范围（用long long确保不溢出）
            long long left = x - k;
            long long right = x + k;

            // 二分查找区间[left, right]内的元素总数（nums元素是int，比较时自动转long long）
            auto l = lower_bound(nums.begin(), nums.end(), left);
            auto r = upper_bound(nums.begin(), nums.end(), right);
            int total_possible = r - l;

            // 原数组中x的数量（x若超出int范围，original为0）
            int original = (x >= INT_MIN && x <= INT_MAX) ? freq.count((int)x) ? freq[(int)x] : 0 : 0;

            // 未被操作的x的最大数量（不超过剩余元素数）
            int s = min(original, remain);

            // 可通过操作变为x的元素数量（区间内减去未操作的x）
            int available = total_possible - s;

            // 实际能操作成x的数量（不超过操作次数）
            int d = min(numOperations, available);

            // 更新最大频率
            max_freq = max(max_freq, s + d);
        }

        return max_freq;
    }
};